

//力扣61. 旋转链表
import java.util.*;
class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head==null){
            return null;
        }
        ListNode cur=head;
        int len=0;
        while(cur!=null){
            len++;
            cur=cur.next;
        }
        k=len>k?k:(k%len);
        int x=(int)Math.abs(len-k);
        ListNode leftNode=new ListNode(-1);
        ListNode rightNode=new ListNode(-1);
        ListNode left=leftNode,right=rightNode;

        while(head!=null){
            if(x>0){
                left.next=head;
                left=left.next;
                x--;
            }else{
                right.next=head;
                right=right.next;
            }
            head=head.next;
        }
        left.next=null;
        right.next=leftNode.next;
        return rightNode.next;
    }
}

//面试题 08.06. 汉诺塔问题
class Solution1 {
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        int n = A.size();
        move(n, A, B, C);  //移动盘子
    }
    public void move(int n, List<Integer> A, List<Integer> B, List<Integer> C) {
        if (n == 1) {
            C.add(A.get(A.size() - 1));  //将A的最后一个盘子移动到C
            A.remove(A.size() - 1);      //移除A的最后一个盘子
            return;
        } else {
            move(n - 1, A, C, B);       //将A上面n-1个通过C移到B
            C.add(A.get(A.size() - 1)); //将A最后一个盘子移动到C
            A.remove(A.size() - 1);     //移除A的最后一个盘子
            move(n - 1, B, A, C);       //将B上面n-1个通过A移到C
        }
    }
}

